package org.example.l0;

import org.example.leetcpde.IArray;
import org.junit.jupiter.api.Test;

public class findMedianSortedArrays
        implements IArray {
    @Test
    void findMedianSortedArrays() {
        //        int[] nums1 = parse("[1]");
        //        int[] nums2 = parse("[2,3,4,5,6]");
        int[] nums1 = parse("[1,4]");
        int[] nums2 = parse("[2,3,5,6]");

        double medianSortedArraysV3 = findMedianSortedArrays(nums1, nums2);
        System.out.println(medianSortedArraysV3);
    }

    public double findMedianSortedArrays(int[] nums1,
                                         int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int total = len1 + len2;
        int k = (total + 1) >> 1;

        int n1 = findK(nums1, nums2, k);
        if ((total & 1) == 1) {
            return n1;
        }

        int n2 = findK(nums1, nums2, k + 1);

        return (n1 + n2) / 2.0;
    }

    public int findK(int[] nums1,
                     int[] nums2,
                     int k) {
        for (int i = 0, j = 0, len1 = nums1.length, len2 = nums2.length, used; ; ) {
            if (i == len1) {
                return nums2[j + k - 1];
            }

            if (j == len2) {
                return nums1[i + k - 1];
            }

            if (k == 1) {
                return Math.min(nums1[i], nums2[j]);
            }

            int mid = k >> 1;
            int i2 = Math.min(len1, i + mid) - 1;
            int j2 = Math.min(len2, j + mid) - 1;
            if (nums1[i2] < nums2[j2]) {
                used = i2 - i + 1;
                i = i2 + 1;
            } else {
                used = j2 - j + 1;
                j = j2 + 1;
            }

            k -= used;
        }
    }
}
